package com.gwcloud.leetcode.hot100;

import java.util.HashSet;
import java.util.List;
import java.util.Set;

/** 
* @ClassName   : Leetcode0139 
* @author      : ganwei 
* @date        : 2020年5月21日 
* @Description : TODO 
*/
public class Leetcode0139 {
    /**
     * -解题思路，该题竟然是动态规划
     */
	public boolean wordBreak(String s, List<String> wordDict) {
		Set<String> wordDictSet = new HashSet<String>(wordDict);
		boolean[] dp = new boolean[s.length()+1];
		dp[0] = true;
		
		for(int i = 0; i <= s.length(); i++) {
			for(int j = 0; j < i; j++) {
				if(dp[j] && wordDictSet.contains(s.substring(j, i))) {
					dp[i] = true;
					break;
				}
			}
		}
		
    	return dp[s.length()];
    }
	
	/**
	 * -回溯算法
	 */
	public boolean wordBreak_1(String s, List<String> wordDict) {
		return backtrack(s, new HashSet<String>(wordDict), 0, new Boolean[s.length()]);
	}
	
	public boolean backtrack(String s, Set<String> wordDict, int start, Boolean[] memo) {
		if(start == s.length()) {
			return true;
		}
		if(memo[start] != null) {
			return memo[start];
		}
		
		for(int end = start+1; end <= s.length(); end++) {
			if(wordDict.contains(s.substring(start, end)) && backtrack(s,wordDict,end, memo)) {
				memo[start] = true;
				return true;
			}
		}
		memo[start] = false;
		return false;
		
	}
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	
    }
}
